/*
有一些不规则的硬币。在这些硬币中，prob[i] 表示第 i 枚硬币正面朝上的概率。

请对每一枚硬币抛掷 一次，然后返回正面朝上的硬币数等于 target 的概率。

 

示例 1：

输入：prob = [0.4], target = 1
输出：0.40000
示例 2：

输入：prob = [0.5,0.5,0.5,0.5,0.5], target = 0
输出：0.03125
 

提示：

1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
如果答案与标准答案的误差在 10^-5 内，则被视为正确答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/toss-strange-coins
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{

public:
    double probabilityOfHeads(vector<double> &prob, int target)
    {
        vector<double> dp(target + 1);
        dp[0] = 1;
        double old1 = 0, old2 = 0;
        for (int i = 0; i < prob.size(); i++)
        {
            if (prob[i] == 0)
                continue;
            old1 = dp[0];
            for (int j = 1; j < dp.size() && j <= i + 1; j++)
            {
                old2 = dp[j];
                dp[j] = old1 * prob[i] + dp[j] * (1 - prob[i]);
                old1 = old2;
            }
            dp[0] *= 1 - prob[i];
        }
        return dp[dp.size() - 1];
    }
    //别的方案
    double probabilityOfHeadsAnother(vector<double> &prob, int target)
    {
        vector<vector<double>> dp(prob.size() + 1, vector<double>(target + 1));
        dp[0][0] = 1.0;
        for (int i = 1; i <= prob.size(); i++)
        {
            for (int j = 0; j <= min(i, target); j++)
            {
                if (j == 0)
                    dp[i][j] = dp[i - 1][j] * (1 - prob[i - 1]);
                else
                {
                    dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]);
                }
            }
        }
        return dp[prob.size()][target];
    }
};